package evaluation;

import java.util.Stack;

/**
 * 回文问题
 */
public class PalindromeQuestion {

    public static void main(String[] args) {
        Node head = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(1);
        Node node3 = new Node(2);

        head.setNext(node1);
        node1.setNext(node2);
        node2.setNext(node3);
        System.out.println(isPalindrome3(head));
    }

    static class Node {
        private int Data;// 数据域
        private Node Next;// 指针域

        public Node(int Data) {
            // super();
            this.Data = Data;
        }

        public int getData() {
            return Data;
        }

        public void setData(int Data) {
            this.Data = Data;
        }

        public Node getNext() {
            return Next;
        }

        public void setNext(Node Next) {
            this.Next = Next;
        }
    }

    public static boolean isPalindrome1(Node head) {
        Stack<Node> stack = new Stack<Node>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.Next;
        }
        while (head != null) {
            if (head.Data != stack.pop().Data) {
                return false;
            }
            head = head.Next;
        }
        return true;
    }

    public static boolean isPalindrome2(Node head) {
        if (head == null || head.Next == null) {
            return true;
        }
        Node right = head.Next;
        Node cur = head;
        while (cur.Next != null && cur.Next.Next != null) {
            right = right.Next;
            cur = cur.Next.Next;
        }
        Stack<Node> stack = new Stack<>();
        while (right != null) {
            stack.push(right);
            right = right.Next;
        }
        while (!stack.isEmpty()) {
            if (head.Data != stack.pop().Data) {
                return false;
            }
            head = head.Next;
        }
        return true;
    }

    public static boolean isPalindrome3(Node head) {
        if (head == null || head.Next == null) {
            return true;
        }
        Node n1 = head;
        Node n2 = head;
        while (n2.Next != null && n2.Next.Next != null) {
            n1 = n1.Next;
            n2 = n2.Next.Next;
        }
        n2 = n1.Next;
        n1.Next = null;
        Node n3 = null;
        while (n2 != null) {
            n3 = n2.Next;
            n2.Next = n1;
            n1 = n2;
            n2 = n3;
        }
        n3 = n1;
        n2 = head;
        boolean res =true;
        while (n1 !=null && n2 !=null){
            if (n1.Data != n2.Data){
                res = false;
                break;
            }
            n1 =n1.Next;
            n2=n2.Next;
        }
        n1=n3.Next;
        n3.Next = null;
        while (n1 != null){
            n2 = n1.Next;
            n1.Next = n3;
            n3 = n1;
            n1 =n2;
        }
        return res;
    }
}
